package com.dmall.chapter08.section04;

import com.dmall.chapter02.section09.Graph;

import java.util.Arrays;

/**
 * 寻找图的桥
 *
 * @author wx
 * @date 2020-03-15 19:40:06
 */
public class FindBridges2 {
    private Graph G;
    private boolean[] visited;
    private int[] ord;
    private int[] low;
    private int order = 0;

    public FindBridges2(Graph G) {
        this.G = G;
        this.visited = new boolean[G.V()];
        this.ord = new int[G.V()];
        this.low = new int[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                dfs(v, v);
            }
        }
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        ord[v] = order;
        low[v] = order;
        order++;
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
            } else if (w != parent && low[v] > low[w]) {
                low[v] = low[w];
            }
        }
        if (low[v] < low[parent]) {
            low[parent] = low[v];
        }
    }

    public boolean hasBridge() {
        for (int i = 1; i < low.length; i++) {
            if (low[i] != low[i - 1]) {
                return true;
            }
        }
        return false;
    }

    public boolean isBridge(int v, int w) {
        return low[v] != low[w];
    }

    public static void main(String[] args) {
        String filename = FindBridges2.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename);
        FindBridges2 fb1 = new FindBridges2(g);
        System.out.println("ord: " + Arrays.toString(fb1.ord));
        System.out.println("low: " + Arrays.toString(fb1.low));
        System.out.println(fb1.hasBridge());
        System.out.println(fb1.isBridge(0, 1));
        System.out.println(fb1.isBridge(3, 5));

        System.out.println();

        String filename1 = FindBridges2.class.getClassLoader().getResource("tree.txt").getPath();
        Graph g1 = new Graph(filename1);
        FindBridges2 fb2 = new FindBridges2(g1);
        System.out.println("ord: " + Arrays.toString(fb2.ord));
        System.out.println("low: " + Arrays.toString(fb2.low));
        System.out.println(fb2.hasBridge());
        System.out.println(fb2.isBridge(0, 1));
        System.out.println(fb2.isBridge(3, 5));
    }
}
